package fun.coding.leetcode;

import java.util.Stack;

public class ValidateBinarySearchTree {

	public static void main(String[] args) {
		// System.out.println(Integer.MAX_VALUE);
		TreeNode root = new TreeNode(1);
		TreeNode left = new TreeNode(2);
		root.left = left;
		
		ValidateBinarySearchTree ins = new ValidateBinarySearchTree();
		System.out.println(ins.isValidBST(root));
	}
	
	
	public boolean isValidBST(TreeNode root) {
		if (root == null) return true;
		
		Stack<TreeNode> stack = new Stack<TreeNode>();
		
		TreeNode cur = root;
		TreeNode lastVisited = null;
		while (!stack.isEmpty() || cur != null) {
			if (cur != null) {
				stack.push(cur);
				cur = cur.left;
			} else {
				TreeNode t = stack.pop();
				
				if (lastVisited != null && t.val <= lastVisited.val) {
					return false;
				}
				lastVisited = t;
				cur = t.right;
			}
		}
		return true;
	}
	
	/*
	// A recursion solution keep a last visited Node
	private TreeNode lastVisited = null;
	
	public boolean isValidBST(TreeNode root) {
		if (root == null) return true;
		
		if (!isValidBST(root.left)) return false;
		
		if (this.lastVisited != null && this.lastVisited.val >= root.val) {
			return false;
		}
		
		lastVisited = root;
		return  isValidBST(root.right);
	}
	
	// This solution logically works, but cannot work with the case that if the tree has Interger.MIN or MAX value.
	public boolean isValidBSTCanNotPass(TreeNode root) {
		// Change it to Long will work for int case
		return helper(root, Long.MIN_VALUE, Long.MAX_VALUE);
	}
	
	public boolean helper(TreeNode root, long min, long max) {
		if (root == null) return true;
		
		if (root.val > min && root.val < max) {
			return helper(root.left, min, Math.min(root.val, max)) && helper(root.right, Math.max(root.val, min), max);	
		} else {
			return false;
		}
	}
	*/

	/* not very good, doesn't really matter 
	public boolean isValidBST(TreeNode root) {
		// won't pass OJ
		TreeNode lastVisited = new TreeNode(Integer.MIN_VALUE);
		return dfsHelper(lastVisited, root);
	}
	
	private boolean dfsHelper(TreeNode lastVisited, TreeNode root) {
		if (root == null) return true;
		
		if (!dfsHelper(lastVisited, root.left)) return false;
		
		if (lastVisited.val >= root.val) {
			return false;
		}
		
		// Note, it won't work if directly assign like lastVisited = root;
		lastVisited.val = root.val;
		return  dfsHelper(lastVisited, root.right);
	}
	*/
}
